/*
 *https://leetcode.cn/problems/number-of-digit-one/description/
 *面试题 17.06. 2出现的次数
 *difficult 吴朝泽 2024.9.20
 *数位DP
 代码思想基本和 lc233 一样
*/


class Solution {
public:
    int arr[20];
    long long dp[20][20];
    //pos 表示当前的位数，pre 表示已统计的 2 的个数，flag 表示填的数字大小是否受到限制
    long long DFS(int pos, int pre, bool flag)
    {
        //这里要注意返回的是 pre 而不是 1，因为到达了最后一位应该返回前面所有位的 2 的数量
        if(pos == 0)  return pre;
        
        if(!flag && dp[pos][pre] != -1)   return dp[pos][pre];

        int max_num = flag ? arr[pos] : 9;
        int res = 0;

        for(int i = 0; i <= max_num; ++i)
        {
            if(i == 2)  res += DFS(pos-1, pre+1, flag && i == max_num);
            else res += DFS(pos-1, pre, flag && i == max_num);
        }

        if(!flag)  dp[pos][pre] = res;
        return res;
    }

    long long check(int x)
    {
        int pos = 0;
        while(x)
        {
            arr[++pos] = x % 10;
            x /= 10;
        }
        return DFS(pos, 0, 1);
    }

    int numberOf2sInRange(int n) 
    {
        memset(dp, -1, sizeof(dp));
        return check(n);
    }
};
